package code3;

import java.util.Arrays;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/16 11:19
 */
class Solution {
    int res = 0;
    public int reversePairs(int[] nums) {

        res = 0;
        sort(nums);
        return res;
    }

    public void sort(int[] arr){
        mergesort(arr,0,arr.length-1);
    }


    public void mergesort(int[] arr,int left,int right){
        if(left>=right){
            return ;
        }

        int mid = left+(right -left)/2;
        mergesort(arr,left,mid);
        mergesort(arr,mid+1,right);
        merge(arr,left,mid,right);
    }

    private void merge(int[] arr, int left, int mid, int right) {

        int[] temp = Arrays.copyOfRange(arr,left,right+1);

        int i = left;
        int j = mid+1;
        for (int k = left; k <= right ; k++) {
            if( i > mid){
                arr[k]=temp[j-left];
                j++;
            }else if(j > right){
                arr[k]=temp[i -left];
                i++;
            }else if(temp[i-left] <=temp[j-left]){ //注意这里
                arr[k]=temp[i-left];
                i++;
            }else{//取右边的值的时候，就有逆序对了
                res+= mid-i+1;
                arr[k]=temp[j-left];
                j++;
            }

        }
    }

    public static void main(String[] args) {
//        int []  arr = {1,9,4,3,6,5,7};
//        int []  arr = {1,3,2,3,1};
//        new Solution().sort(arr);
//        for (int i = 0; i < arr.length; i++) {
//            System.out.print(arr[i]+" ");
//        }

        System.out.println("========================");
//        int []  arr = {7,5,6,4};
        int []  arr2 = {1,3,2,3,1}; //4
        int i = new Solution().reversePairs(arr2);
        System.out.println(i);
    }
}
